import java.util.Random;

public class L_2_2 {
    /**
     * 前缀和数组
     * 当我们需要对一个数组中的L-R范围求和时,且这个求和操作量非常大,如何做到快速查询呢
     * 1.建立二维数组,将所有的求和值都列出,之后直接调用
     * 2.建立前缀和数组,也就是0-n的求和数组,这是一个一维数组,假设需要求x-y的和,那么我们只需要调用int[n=y] - int[n=x]的值,也就是0-y减去0-x的值
     */

    public static int[] And2(int[] arr) {
        int[] sub = new int[arr.length];
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum = 0;
            for (int j = 0; j <= i; j++) {
                sum += arr[j];
            }
            sub[i] = sum;
        }
        return sub;
    }

    public static int[][] And1(int[] arr) {
        int[][] sub = new int[arr.length][arr.length];
        int sum = 0, i = 0, j = 0;
        for (i = 0; i < arr.length; i++) {
            sum = 0;
            for (j = i; j < arr.length; j++) {

                    sum += arr[j];
                sub[i][j] = sum;
            }
        }

        return sub;
    }



    public static void printArr1(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(String.format("%3d",arr[i][j])+" ");
            }
            System.out.println();
        }

    }

    public static void printArr2(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int sub = 0;
        int[] num1 = {8,56,48,-78,7,-8,76,78,33,-11,5};
        int[] num2 = {8,56,48,-78,7,-8,76,78,33,-11,5,7,77,-8,6,46,-6,74,86,7};
        int[] and2 = And2(num1);
        int[][] and1 = And1(num2);
//        printArr1(and1);
        printArr2(and2);
        for (int i = 0; i < 5; i++) {
            int x1 = new Random().nextInt(10);//返回值在0-9之间
            int y1 = new Random().nextInt(10);//返回值在0-9之间
            int x2 = new Random().nextInt(20);//返回值在0-19之间
            int y2 = new Random().nextInt(20);//返回值在0-19之间
            if (x1 >= y1) {
                if(y1 == 0 )
                    sub = and2[x1];
                else
                    sub = and2[x1] - and2[y1-1];
            } else {
                if(x1 == 0)
                    sub = and2[y1];
                else
                    sub = and2[y1] - and2[x1-1];
            }

            if (x2 <= y2) {
                sub = and1[x2][y2];
            } else {
                sub = and1[y2][x2];
            }

//            System.out.println("x1 = "+x1+" ,y1 = "+y1+" ,sub = "+sub);
            System.out.println("x2 = "+x2+" ,y2 = "+y2+" ,sub = "+sub);
        }
    }
}
